package leetcode_周赛._2022._202201._09;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/1/9 11:00
 * 最少交换次数来组合所有的 1 II
 * 算法：滑动窗口
 * 找到含 1 最多的窗口
 *  遍历数组，一直以 1 的个数大小的滑动窗口向后移动
 *  寻找含 1 最多的窗口
 * ans = 数组中 1 的个数 - 含 1 最多的滑动窗口中 1 的个数
 */
public class _5977 {
    public static void main(String[] args) {
        System.out.println(new _5977().minSwaps(new int[]{1, 1, 0, 0, 1}));
    }

    public int minSwaps(int[] nums) {
        int num = 0, n = nums.length;
        for (int i = 0; i < n; i++) if (nums[i] == 1) ++num;
        if (num == 0 || num == n) return 0;
        int cnt = 0;
        for (int i = 0; i < num; i++) if (nums[i] == 1) ++cnt;
        int max = cnt;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) --cnt;
            if (nums[(i + num) % n] == 1) ++cnt;
            max = Math.max(max, cnt);
        }
        return num - max;
    }

}
